# 70/100 栈-最小栈
# leetcode第155题: https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/27


class MinStack:
    def __init__(self):
        self._list = []
        self._top = None

    def push(self, val: int) -> None:
        self._list.append(val)
        self._top = self._list[-1]

    def pop(self) -> None:
        if self._list:
            self._list.pop()
            if self._list:  # 弹出后
                self._top = self._list[-1]
            else:
                self._top = None
        else:
            raise RuntimeError("Stack is Empty")

    def top(self) -> int:
        return self._top

    def getMin(self) -> int:
        _min = float('inf')
        for v in self._list:
            _min = min(_min, v)
        return _min


class MinStackOpt:
    def __init__(self):
        self._list = []
        self._top = None

    def push(self, val: int) -> None:
        self._list.append(val)
        self._top = self._list[-1]

    def pop(self) -> None:
        if self._list:
            self._list.pop()
            if self._list:  # 弹出后
                self._top = self._list[-1]
            else:
                self._top = None
        else:
            raise RuntimeError("Stack is Empty")

    def top(self) -> int:
        return self._top

    def getMin(self) -> int:
        _min = float('inf')
        for v in self._list:
            _min = min(_min, v)
        return _min


if __name__ == '__main__':
    obj = MinStack()
    obj.push(3)
    obj.push(5)
    obj.push(6)
    obj.push(1)
    print(obj.getMin())
    print(obj.top())
    obj.pop()
    print(obj.getMin())
    print(obj.top())

    print("#" * 15)
    obj = MinStackOpt()
    obj.push(3)
    obj.push(5)
    obj.push(6)
    obj.push(1)
    print(obj.getMin())
    print(obj.top())
    obj.pop()
    print(obj.getMin())
    print(obj.top())
